#include "mcmcMoveBoundary.h"
#include "mcmcLayerRegion.h"
#include "mcRand.h"

/////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////
// construction & destruction
MbNodeTopologyRecord::MbNodeTopologyRecord()
{
	// initilization
	pnode = NULL;
	id_node = -1;
	pver = NULL;
	for (int i=0; i<4; i++)
		connections_after[i] = 0;
	deleted = false;
}

// operations
void MbNodeTopologyRecord::Init(const McImagePoint &grid1, MbRelativePosition &rp, MCMC_Layer_Regions *player_region1)
{
	player_region = player_region1;
	grid = grid1;
	id_node = player_region->mx_label_id_nodes(grid.Row(), grid.Col());
	pnode = player_region->GetNode(id_node);
	if (pnode == NULL)
	{
		// create a new node
		id_node = player_region->NewNode();
		pnode = player_region->GetNode(id_node);
		assert(pnode != NULL);

		pnode->SetX(grid.X());
		pnode->SetY(grid.Y());

		player_region->mx_label_id_nodes(grid.Row(), grid.Col()) = id_node;
	}

	pver = player_region->GetVertex(player_region->mx_label_id_vertices(grid.Row(), grid.Col()));

	for (int k=0; k<4; k++)
	{
		rp.GetGridPos(grid_neighbors[k], grid, k);
		if (GetCSegWithNeighbor(k) != NULL)
			connections_after[k] = 1;
		else
			connections_after[k] = 0;
	}
}

inline MCMC_Contour_Segment* MbNodeTopologyRecord::GetCSegWithNeighbor(const int i)
{
	assert(i>=0 && i<4);
	return player_region->GetCSeg(player_region->cseg_on_grid.CSegId(grid, grid_neighbors[i]));

}

inline int MbNodeTopologyRecord::GetNodeNeightbor(const int i)
{
	assert(i>=0 && i<4);
	if (player_region->mx_label_id_nodes.Valid(grid_neighbors[i].Row(), grid_neighbors[i].Col()))
		return player_region->mx_label_id_nodes(grid_neighbors[i].Row(), grid_neighbors[i].Col());
	else
		return -1;
}


int MbNodeTopologyRecord::NumConnections(void)
{
	int num=0;

	for (int k=0; k<4; k++)
		if (connections_after[k])
			num++;
	return num;
}

int MbNodeTopologyRecord::NumAllConnections(void)
{
	int num=0;

	for (int k=0; k<4; k++)
		if (connections_after[k] || GetCSegWithNeighbor(k) != NULL)
			num++;
	return num;
}


///////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

MCMC_MoveBoundary::MCMC_MoveBoundary(MCMC_Layer_Regions *player_region1)
{
	player_region=player_region1;

	int i,j;

	int left_right_temp[3][2]={{0,1},{4,1},{2,1}};
	for (j=0; j<3; j++)
		for (i=0; i<2; i++)
			left_right[j][i] = left_right_temp[j][i];

	signs_connections[0] = MC_MB_UP;
	signs_connections[1] = MC_MB_RIGHT;
	signs_connections[2] = MC_MB_DOWN;
	signs_connections[3] = MC_MB_LEFT;
}

void MCMC_MoveBoundary::UpdateCSegIdOnGrid(MCMC_Contour_Segment *pcseg, const int id_replace)
{
	if (pcseg == NULL)
		return;

	MCMC_Node *pnode1,*pnode2;

	pnode1 = player_region->GetNode(pcseg->GetFirstNode());
	pnode2 = player_region->GetNode(pcseg->GetNextNode());

	while (pnode1!=NULL && pnode2!=NULL)
	{
		player_region->cseg_on_grid.CSegId(pnode1->GridRow(), pnode1->GridCol(), pnode2->GridRow(), pnode2->GridCol()) = id_replace;

		pnode1 = pnode2;
		pnode2 = player_region->GetNode(pcseg->GetNextNode());
	}
	if (pcseg->node[0] == pcseg->node[1])
	{
		// self-closed contour
		pnode1 = player_region->GetNode(pcseg->node[1]);
		pnode2 = player_region->GetNode(pcseg->extn[1]);
		assert(pnode1!=NULL && pnode2!=NULL);
		player_region->cseg_on_grid.CSegId(pnode1->GridRow(), pnode1->GridCol(), pnode2->GridRow(), pnode2->GridCol()) = id_replace;
	}
}


// operations related to moving nodes
//  left_or_right: 0   left,  1  right
//   return: the next node to move
int	MCMC_MoveBoundary::MoveNodes(MCMC_Contour_Segment *pcseg, const int id_node1, const int id_node2, const uchar left_or_right, const bool swaped)
{
	MCMC_Node		*pnode1,*pnode2;
	uchar			direction;
	int			space;

	pnode1 = player_region->GetNode(id_node1);
	pnode2 = player_region->GetNode(id_node2);

	if (pnode1==NULL || pnode2==NULL)
		return 0;		// not valid
	if (pnode1->GetX()==pnode2->GetX())
	{
		space = pnode2->GridCol()-pnode1->GridCol();
		if (space == 1)
			direction = 0;	// horizontal
		else if (space == -1)
		{
			return MoveNodes(pcseg, id_node2, id_node1, 1-left_or_right, true);
		}
		else
			return 0;
	}
	else if (pnode1->GetY()==pnode2->GetY())
	{
		space = pnode2->GridRow()-pnode1->GridRow();
		if (space == 1)
			direction = 1;	// horizontal
		else if (space == -1)
		{
			return MoveNodes(pcseg, id_node2, id_node1, 1-left_or_right, true);
		}
		else
			return 0;
	}
	else
		return 0;		// not valid

	McImagePoint	grid_node1_new,grid_node2_new;
	int				i_change,j_change,i_from,j_from;
	char			go_plus_or_minus;

	// the new position
	if (direction == 0)
	{
		// on the boundary?
		if (pnode1->GridRow()==0 || pnode1->GridRow()==player_region->height)
			return 0;	// boundary nodes are not allowed to be moved

		grid_node1_new.SetCol(pnode1->GridCol());
		grid_node2_new.SetCol(pnode2->GridCol());

		if (left_or_right == MB_CSEG_LEFT)
		{												//                     __
			grid_node1_new.SetRow(pnode1->GridRow()-1);	//left  1|__|   ->   1|  |
			j_change = grid_node1_new.Row();
			go_plus_or_minus = -1;
		}
		else
		{												//        __
			grid_node1_new.SetRow(pnode1->GridRow()+1);	//right 1|  |   ->   1|__|
			j_change = grid_node1_new.Row()-1;
			go_plus_or_minus = 1;

		}
		grid_node2_new.SetRow(grid_node1_new.Row());
		i_change = min(grid_node1_new.Col(), grid_node2_new.Col());

		j_from = j_change-go_plus_or_minus;
		i_from = i_change;
	}
	else
	{
		// on the boundary?
		if (pnode1->GridCol()==0 || pnode1->GridCol()==player_region->width)
			return 0;	// boundary nodes are not allowed to be moved

		grid_node1_new.SetRow(pnode1->GridRow());
		grid_node2_new.SetRow(pnode2->GridRow());

		if (left_or_right == MB_CSEG_LEFT)				// 1_         _1
		{												// |    ->     |
			grid_node1_new.SetCol(pnode1->GridCol()+1);	// |_         _|

			i_change = grid_node1_new.Col()-1;
			go_plus_or_minus = 1;
		}
		else
		{												// _1         1_
										 				//  |   ->    |
			grid_node1_new.SetCol(pnode1->GridCol()-1);	// _|         |_

			i_change = grid_node1_new.Col();
			go_plus_or_minus = -1;
		}
		grid_node2_new.SetCol(grid_node1_new.Col());
		j_change = min(grid_node1_new.Row(), grid_node2_new.Row());

		j_from = j_change;
		i_from = i_change-go_plus_or_minus;
	}

	// check whether this move is legitimate or not
	if (!IsMoveAllowed(j_change, i_change, direction, go_plus_or_minus))
		return 0; // don't do anything

	bool bchanged = swaped;

	if ((direction==0 && go_plus_or_minus==-1) || (direction==1 && go_plus_or_minus==1))
	{
		// set the basic information necessary
		node1.id_node = id_node1;
		node1.grid.SetRow(pnode1->GridRow());
		node1.grid.SetCol(pnode1->GridCol());
		node1.pnode = player_region->GetNode(id_node1);

		node2.id_node = id_node2;
		node2.grid.SetRow(pnode2->GridRow());
		node2.grid.SetCol(pnode2->GridCol());
		node2.pnode = player_region->GetNode(id_node2);

		node1_to.grid = grid_node1_new;
		node2_to.grid = grid_node2_new;
	}
	else
	{
		node2.id_node = id_node1;
		node2.grid.SetRow(pnode1->GridRow());
		node2.grid.SetCol(pnode1->GridCol());
		node2.pnode = player_region->GetNode(id_node1);

		node1.id_node = id_node2;
		node1.grid.SetRow(pnode2->GridRow());
		node1.grid.SetCol(pnode2->GridCol());
		node1.pnode = player_region->GetNode(id_node2);

		node2_to.grid = grid_node1_new;
		node1_to.grid = grid_node2_new;

		bchanged = !bchanged;
	}
	// move the nodes
	MakeTheMove(pcseg, j_from, i_from);

	// update the labels
	player_region->mx_label_id_aregions(j_change, i_change) = player_region->mx_label_id_aregions(j_from, i_from);

//	assert(CheckConsistencyOfTopologyRecord());

	if (!bchanged)
	{
		p_nodes_next_to_move[0] = player_region->mx_label_id_nodes(node2_to.grid.Row(), node2_to.grid.Col());
		p_nodes_next_to_move[1] = player_region->mx_label_id_nodes(node2.grid.Row(), node2.grid.Col());
		p_nodes_next_to_move[2] = player_region->mx_label_id_nodes(node1_to.grid.Row(), node1_to.grid.Col());
		p_nodes_next_to_move[3] = player_region->mx_label_id_nodes(node1.grid.Row(), node1.grid.Col());
	}
	else
	{
		p_nodes_next_to_move[0] = player_region->mx_label_id_nodes(node1_to.grid.Row(), node1_to.grid.Col());
		p_nodes_next_to_move[1] = player_region->mx_label_id_nodes(node1.grid.Row(), node1.grid.Col());
		p_nodes_next_to_move[2] = player_region->mx_label_id_nodes(node2_to.grid.Row(), node2_to.grid.Col());
		p_nodes_next_to_move[3] = player_region->mx_label_id_nodes(node2.grid.Row(), node2.grid.Col());
	}

	return 1;
}


// three possible situations that will make disconncted regions will not be allowed
/*
      2         1        1                   3 4 5
    1 1 1     1 1 3    2 1 1   position:     0 1 2
      0         0        0
*/
bool MCMC_MoveBoundary::IsMoveAllowed(const int j_change, const int i_change, const uchar horizontal_or_vertical,
									  const char go_plus_or_minus)
{
	int	i,j,k,i_from,j_from;

	k = 0;
	if (horizontal_or_vertical == 0)
	{
		// horizontal
		for (j=j_change; j!=j_change+2*go_plus_or_minus; j+=go_plus_or_minus)
			for (i=i_change+go_plus_or_minus; i!=i_change-2*go_plus_or_minus; i-=go_plus_or_minus)
			{
				if (player_region->mx_label_id_aregions.Valid(j, i))
					labels[k++] = player_region->mx_label_id_aregions(j, i);
				else
					labels[k++] = -1;
			}
		j_from = j_change-go_plus_or_minus;
		i_from = i_change;
	}
	else
	{
		// vertical
		for (i=i_change; i!=i_change+2*go_plus_or_minus; i+=go_plus_or_minus)
			for (j=j_change-go_plus_or_minus; j!=j_change+2*go_plus_or_minus; j+=go_plus_or_minus)
			{
				if (player_region->mx_label_id_aregions.Valid(j, i))
					labels[k++] = player_region->mx_label_id_aregions(j, i);
				else
					labels[k++] = -1;
			}
		j_from = j_change;
		i_from = i_change-go_plus_or_minus;
	}

	// make sure the move is happening on the boundary
	assert(player_region->mx_label_id_aregions(j_from, i_from) != player_region->mx_label_id_aregions(j_change, i_change));

	int label_from;

	label_from = player_region->mx_label_id_aregions(j_from, i_from);
	// won't cause a hole
	if (labels[4]==label_from && (labels[0]!=label_from && labels[2]!=label_from))
		return false;

	// check case 2
	if (labels[0]==labels[1] && labels[1]==labels[4] && labels[1]!=labels[3])
		return false;

	// check case 3
	if (labels[1]==labels[2] && labels[1]==labels[4] && labels[1]!=labels[5])
		return false;

	// the last pixel for the region is not allowed to be deleted
	if (labels[0]!=labels[1] && labels[4]!=labels[1] && labels[2]!=labels[1])
		return false;
	
	if (labels[5]==label_from && labels[4]!=labels[5] && labels[2]!=labels[5])
		return false;

	if (labels[3]==label_from && labels[4]!=labels[3] && labels[0]!=labels[3])
		return false;

	// check case 1
	if ( (labels[0]==labels[1] && labels[1]==labels[2]) &&
		!(labels[0]==labels[3] && labels[3]==labels[4] && labels[4]==labels[5] && labels[5]==labels[2]))
		return false;

	return true;
}

void MCMC_MoveBoundary::MakeTheMove(MCMC_Contour_Segment* pcseg, const int j_from, const int i_from)
{
	MCMC_Vertex  *pver;

	// there are four situations in total
	if (player_region->mx_label_id_nodes(node1_to.grid.Row(), node1_to.grid.Col()) < 0 &&
		player_region->mx_label_id_nodes(node2_to.grid.Row(), node2_to.grid.Col()) < 0)
	{
		// case 1:

		// this is the simplest case, there are no existing nodes at the position to which the new boundary is moving
		// this is probably the most popular case
		MoveMakeTwoNodesCase1(pcseg);
	}
	else if (player_region->mx_label_id_nodes(node1_to.grid.Row(), node1_to.grid.Col()) >= 0 &&
			 player_region->mx_label_id_nodes(node2_to.grid.Row(), node2_to.grid.Col()) < 0 &&
			 (player_region->mx_label_id_vertices(node1.grid.Row(), node1.grid.Col())<0 || pcseg->SelfClosed()))
	{
		// case 2:
		pver = player_region->GetVertex(player_region->mx_label_id_vertices(node1.grid.Row(), node1.grid.Col()));
		if (pver==NULL || pver->Degree()<=1)
			MoveMakeTwoNodesCase2(pcseg, node1, node2, node1_to, node2_to);
		else
			MoveMakeTwoNodesCase3(pcseg, j_from, i_from);
	}
	else if (player_region->mx_label_id_nodes(node2_to.grid.Row(), node2_to.grid.Col()) >= 0 &&
			 player_region->mx_label_id_nodes(node1_to.grid.Row(), node1_to.grid.Col()) < 0 &&
			 (player_region->mx_label_id_vertices(node2.grid.Row(), node2.grid.Col())<0 || pcseg->SelfClosed()))
	{
		// case 2:
		pver = player_region->GetVertex(player_region->mx_label_id_vertices(node2.grid.Row(), node2.grid.Col()));
		if (pver==NULL || pver->Degree()<=1)
			MoveMakeTwoNodesCase2(pcseg, node2, node1, node2_to, node1_to);
		else
			MoveMakeTwoNodesCase3(pcseg, j_from, i_from);
	}
	else
		MoveMakeTwoNodesCase3(pcseg, j_from, i_from);
}

void MCMC_MoveBoundary::MoveMakeTwoNodesCase1(MCMC_Contour_Segment* pcseg)
{
	// create two new nodes
	node1_to.id_node = player_region->NewNode();
	node1_to.pnode = player_region->GetNode(node1_to.id_node);
	assert(node1_to.pnode != NULL);

	node2_to.id_node = player_region->NewNode();
	node2_to.pnode = player_region->GetNode(node2_to.id_node);
	assert(node2_to.pnode != NULL);

	// coordinates
	node1_to.pnode->SetX(node1_to.grid.X());
	node1_to.pnode->SetY(node1_to.grid.Y());
	node2_to.pnode->SetX(node2_to.grid.X());
	node2_to.pnode->SetY(node2_to.grid.Y());

	// link the connections
	if (pcseg->IsFromNode1ToNode2(node1.pnode, node1.id_node, node2.pnode, node2.id_node))
	{
		// direction is from node1 to node2
		node1.pnode->link[0] = node1_to.id_node;

		node1_to.pnode->link[1] = node1.id_node;
		node1_to.pnode->link[0] = node2_to.id_node;

		node2_to.pnode->link[1] = node1_to.id_node;
		node2_to.pnode->link[0] = node2.id_node;

		node2.pnode->link[1] = node2_to.id_node;

		// if node2 is the second node to the beginning
		if (pcseg->extn[0] == node2.id_node)
			pcseg->extn[0] = node1_to.id_node;
		// if node1 is the second node to the end
		if (pcseg->extn[1] == node1.id_node)
			pcseg->extn[1] = node2_to.id_node;
	}
	else
	{
		// direction is from node2 to node1
		node1.pnode->link[1] = node1_to.id_node;

		node1_to.pnode->link[0] = node1.id_node;
		node1_to.pnode->link[1] = node2_to.id_node;

		node2_to.pnode->link[0] = node1_to.id_node;
		node2_to.pnode->link[1] = node2.id_node;

		node2.pnode->link[0] = node2_to.id_node;

		// if node2 is the second node to the beginning
		if (pcseg->extn[0] == node1.id_node)
			pcseg->extn[0] = node2_to.id_node;
		// if node1 is the second node to the end
		if (pcseg->extn[1] == node2.id_node)
			pcseg->extn[1] = node1_to.id_node;
	}

	// update the labels
	player_region->mx_label_id_nodes(node1_to.grid.Row(), node1_to.grid.Col()) = node1_to.id_node;
	player_region->mx_label_id_nodes(node2_to.grid.Row(), node2_to.grid.Col()) = node2_to.id_node;

	player_region->cseg_on_grid.CSegId(node1.grid, node1_to.grid) = pcseg->Id();
	player_region->cseg_on_grid.CSegId(node1_to.grid, node2_to.grid) = pcseg->Id();
	player_region->cseg_on_grid.CSegId(node2_to.grid, node2.grid) = pcseg->Id();
	player_region->cseg_on_grid.CSegId(node2.grid, node1.grid) = -1;
}

void MCMC_MoveBoundary::MoveMakeTwoNodesCase2(MCMC_Contour_Segment* pcseg, MbNodeTopologyRecord &node_a1, MbNodeTopologyRecord &node_a2, MbNodeTopologyRecord &node_a1_to, MbNodeTopologyRecord &node_a2_to)
{
	// get the existing node
	node_a1_to.id_node = player_region->mx_label_id_nodes(node_a1_to.grid.Row(), node_a1_to.grid.Col());
	node_a1_to.pnode = player_region->GetNode(node_a1_to.id_node);
	assert(node_a1_to.pnode != NULL);

	// create the new node
	node_a2_to.id_node = player_region->NewNode();
	node_a2_to.pnode = player_region->GetNode(node_a2_to.id_node);
	assert(node_a2_to.pnode != NULL);
	// coordinates
	node_a2_to.pnode->SetX(node_a2_to.grid.X());
	node_a2_to.pnode->SetY(node_a2_to.grid.Y());
	// update the labels
	player_region->mx_label_id_nodes(node_a2_to.grid.Row(), node_a2_to.grid.Col()) = node_a2_to.id_node;

	// if node_a1 id the vertex
	node_a1.pver = player_region->GetVertex(player_region->mx_label_id_vertices(node_a1.grid.Row(), node_a1.grid.Col()));
	if (node_a1.pver != NULL)
	{
		// move to node_a2_to
		player_region->mx_label_id_vertices(node_a1.grid.Row(), node_a1.grid.Col()) = -1;
		node_a1.pver->SetX(node_a2_to.grid.X());
		node_a1.pver->SetY(node_a2_to.grid.Y());
		player_region->mx_label_id_vertices(node_a2_to.grid.Row(), node_a2_to.grid.Col()) = node_a1.pver->Id();
	}

	// link the connections
	if (pcseg->IsFromNode1ToNode2(node_a1.pnode, node_a1.id_node, node_a2.pnode, node_a2.id_node))
	{
		// direction is from node_a1 to node_a2
		node_a1_to.pnode->link[0] = node_a2_to.id_node;

		node_a2_to.pnode->link[1] = node_a1_to.id_node;
		node_a2_to.pnode->link[0] = node_a2.id_node;

		node_a2.pnode->link[1] = node_a2_to.id_node;

		if (node_a1.pver != NULL)
		{
			if (pcseg->node[0] == node_a1.id_node)
			{
				pcseg->node[0] = node_a2_to.id_node;
				pcseg->extn[0] = node_a2.id_node;
			}
			if (pcseg->node[1] == node_a1.id_node)
			{
				pcseg->node[1] = node_a2_to.id_node;
				pcseg->extn[1] = node_a1_to.id_node;
			}
		}
	}
	else
	{
		// direction is from node_a2 to node_a1
		node_a1_to.pnode->link[1] = node_a2_to.id_node;

		node_a2_to.pnode->link[0] = node_a1_to.id_node;
		node_a2_to.pnode->link[1] = node_a2.id_node;

		node_a2.pnode->link[0] = node_a2_to.id_node;

		if (node_a1.pver != NULL)
		{
			if (pcseg->node[0] == node_a1.id_node)
			{
				pcseg->node[0] = node_a2_to.id_node;
				pcseg->extn[0] = node_a1_to.id_node;
			}
			if (pcseg->node[1] == node_a1.id_node)
			{
				pcseg->node[1] = node_a2_to.id_node;
				pcseg->extn[1] = node_a2.id_node;
			}
		}
	}

	// if node_a1 is the second node to the end
	if (pcseg->extn[0] == node_a1.id_node)
		pcseg->extn[0] = node_a2_to.id_node;
	if (pcseg->extn[1] == node_a1.id_node)
		pcseg->extn[1] = node_a2_to.id_node;

	// delete node_a1
	player_region->mx_label_id_nodes(node_a1.grid.Row(), node_a1.grid.Col()) = -1;
	player_region->DeleteNodeFromArray(node_a1.id_node);

	player_region->cseg_on_grid.CSegId(node_a2.grid, node_a1.grid) = -1;
	player_region->cseg_on_grid.CSegId(node_a1.grid, node_a1_to.grid) = -1;
	player_region->cseg_on_grid.CSegId(node_a1_to.grid, node_a2_to.grid) = pcseg->Id();
	player_region->cseg_on_grid.CSegId(node_a2_to.grid, node_a2.grid) = pcseg->Id();
}

void MCMC_MoveBoundary::MoveMakeTwoNodesCase3(MCMC_Contour_Segment* pcseg, const int j_from, const int i_from)
{
	MbRelativePosition	rp;

	// the relative positions
	rp.Set(node1.grid, node2.grid, node1_to.grid);

	// the two moving nodes
	node1.Init(node1.grid, rp, player_region);
	node2.Init(node2.grid, rp, player_region);
	// the nodes move to
	node1_to.Init(node1_to.grid, rp, player_region);
	node2_to.Init(node2_to.grid, rp, player_region);

	// change the label
	labels[1] = player_region->mx_label_id_aregions(j_from, i_from);
	// cut the link between node1 and node2
	node1.connections_after[MC_MB_RIGHT] = 0;
	node2.connections_after[MC_MB_LEFT] = 0;

	// two connections on condition
	if (labels[0] == labels[1])
	{
		node1.connections_after[MC_MB_UP] = 0;
		node1_to.connections_after[MC_MB_DOWN] = 0;
	}
	else
	{
		node1.connections_after[MC_MB_UP] = 1;
		node1_to.connections_after[MC_MB_DOWN] = 1;
	}

	if (labels[1] == labels[2])
	{
		node2.connections_after[MC_MB_UP] = 0;
		node2_to.connections_after[MC_MB_DOWN] = 0;
	}
	else
	{
		node2.connections_after[MC_MB_UP] = 1;
		node2_to.connections_after[MC_MB_DOWN] = 1;
	}

	if (labels[1] == labels[4])
	{
		node1_to.connections_after[MC_MB_RIGHT] = 0;
		node2_to.connections_after[MC_MB_LEFT] = 0;
	}
	else
	{
		node1_to.connections_after[MC_MB_RIGHT] = 1;
		node2_to.connections_after[MC_MB_LEFT] = 1;
	}

	if (IsSpecialCase3(pcseg))
		return;

	// create vertices and break contour segments
	CreateVertexAndBreakCSegs(node1, node1_to, node2);
	CreateVertexAndBreakCSegs(node2, node1, node2_to);
	CreateVertexAndBreakCSegs(node2_to, node2, node1_to);
	CreateVertexAndBreakCSegs(node1_to, node2_to, node1);

	// create contour segments
	ConnectContourSegments();
}


void MCMC_MoveBoundary::DeleteTheNodesIfNecessary(MCMC_Contour_Segment* pcseg, MbNodeTopologyRecord &node1, MbNodeTopologyRecord &node2,
									MbNodeTopologyRecord &node1_to, MbNodeTopologyRecord &node2_to, const int id_node_extn)
{
	// Should node1 be deleted?
	if (node1.NumConnections() == 0)
	{
		player_region->DeleteNodeFromArray(node1.id_node);
		player_region->mx_label_id_nodes(node1.grid.Row(), node1.grid.Col()) = -1;
		node1.deleted = true;

		if (node1.pver != NULL)
		{
			// this is a single closed contour
			assert(node2.NumConnections() == 0);
			assert(pcseg->node[0]==pcseg->node[1] && pcseg->end[0]==pcseg->end[1]);

			player_region->mx_label_id_vertices(node1.grid.Row(), node1.grid.Col()) = -1;
			// move vertex to node1_to
			player_region->mx_label_id_vertices(node1_to.grid.Row(), node1_to.grid.Col()) = node1.pver->Id();
			node1.pver->SetX(node1_to.pnode->GetX());
			node1.pver->SetY(node1_to.pnode->GetY());

			pcseg->node[0] = pcseg->node[1] = node1_to.id_node;
			if (pcseg->extn[0] == node2.id_node)
			{
				pcseg->extn[0] = node2_to.id_node;
				pcseg->extn[1] = node1_to.pnode->link[1];
			}
			else
			{
				pcseg->extn[1] = node2_to.id_node;
				pcseg->extn[0] = node1_to.pnode->link[1];
			}
		}
	}
}

// merge the two contour segments into one by id_cseg1
void MCMC_MoveBoundary::MergeSegments(MCMC_Contour_Segment *pcseg1, MCMC_Contour_Segment *pcseg2, MbNodeTopologyRecord &node_a, MbNodeTopologyRecord &node_b)
{
	assert(pcseg1!=NULL && pcseg2!=NULL);

	if ( (pcseg1->node[0]==pcseg2->node[0] && pcseg1->node[1]==pcseg2->node[1]) ||
		 (pcseg1->node[0]==pcseg2->node[1] && pcseg1->node[1]==pcseg2->node[0]))
	{
		// from the same point, to deside which node to merge
		if (pcseg1->node[0] == node_a.id_node && pcseg1->node[1] == node_b.id_node)
		{
			if (node_a.NumConnections() < node_b.NumConnections())
				pcseg1->SwapVertices();
		}
		else if (pcseg1->node[0] == node_b.id_node && pcseg1->node[1] == node_a.id_node)
		{
			if (node_b.NumConnections() < node_a.NumConnections())
				pcseg1->SwapVertices();
		}
		else assert(false);

	}
	
	pcseg2->ChangeStartOfRelatedRegion();
	UpdateCSegIdOnGrid(pcseg2, pcseg1->Id());

	if (pcseg1->node[1]==pcseg2->node[1] || pcseg1->node[0]==pcseg2->node[0])
		pcseg2->SwapVertices();

	MCMC_Node	*pnode_extn,*pnode;
	MCMC_Vertex	*pver1,*pver2;

	if (pcseg1->node[1] == pcseg2->node[0])
	{
		pnode_extn = player_region->GetNode(pcseg1->extn[1]);
		assert(pnode_extn != NULL);
		pnode = player_region->GetNode(pcseg1->node[1]);
		assert(pnode != NULL);
		pnode_extn->link[0] = pcseg1->node[1];
		pnode->link[1] = pcseg1->extn[1];

		pnode_extn = player_region->GetNode(pcseg2->extn[0]);
		assert(pnode_extn != NULL);
		pnode->link[0] = pcseg2->extn[0];
		pnode_extn->link[1] = pcseg1->node[1];


		pcseg1->end[1] = pcseg2->end[1];
		pcseg1->node[1] = pcseg2->node[1];
		pcseg1->extn[1] = pcseg2->extn[1];

		pver1 = player_region->GetVertex(pcseg1->end[1]);
		pver2 = player_region->GetVertex(pcseg2->end[0]);
	}
	else
	{
		assert(pcseg1->node[0] == pcseg2->node[1]);

		pnode_extn = player_region->GetNode(pcseg1->extn[0]);
		assert(pnode_extn != NULL);
		pnode = player_region->GetNode(pcseg1->node[0]);
		assert(pnode != NULL);
		pnode_extn->link[1] = pcseg1->node[0];
		pnode->link[0] = pcseg1->extn[0];

		pnode_extn = player_region->GetNode(pcseg2->extn[1]);
		assert(pnode_extn != NULL);
		pnode->link[1] = pcseg2->extn[1];
		pnode_extn->link[0] = pcseg1->node[0];


		pcseg1->end[0] = pcseg2->end[0];
		pcseg1->node[0] = pcseg2->node[0];
		pcseg1->extn[0] = pcseg2->extn[0];

		pver1 = player_region->GetVertex(pcseg1->end[0]);
		pver2 = player_region->GetVertex(pcseg2->end[1]);
	}

	assert(pver1 != NULL);
	pver1->DeleteCSeg(pcseg2->Id());
	pver1->AddSeg(pcseg1->Id());

	pver2->DeleteCSeg(pcseg1->Id());
	pver2->DeleteCSeg(pcseg2->Id());

	player_region->DeleteCSegFromArray(pcseg2->Id());
}



///////////////////////////////////////////////////////////////
// operations related to moving boundaries
int MCMC_MoveBoundary::BreakContourSegment(MCMC_Contour_Segment *pcseg, MCMC_Vertex *pver1, const int id_node1, const int id_node_ref)
{
	MCMC_Node				*pnode1,*pnode_ref;
	MCMC_Contour_Segment	*pcseg_new;

	pnode1 = player_region->GetNode(id_node1);
	pnode_ref = player_region->GetNode(id_node_ref);
	assert(pcseg!=NULL && pnode1!=NULL && pnode_ref!=NULL);

	MCMC_Vertex *pver_old;
	bool bself_closed=pcseg->SelfClosed();

	pcseg_new = player_region->GetCSeg(player_region->NewCSeg());
	assert(pcseg_new != NULL);

	if (pcseg->IsFromNode1ToNode2(pnode1, id_node1, pnode_ref, id_node_ref))
	{
		pcseg_new->end[1] = pcseg->end[1];
		pcseg_new->node[1] = pcseg->node[1];
		pcseg_new->extn[1] = pcseg->extn[1];
		pcseg_new->end[0]  = pver1->Id();
		pcseg_new->node[0] = id_node1;
		pcseg_new->extn[0] = id_node_ref;

		pcseg->end[1] = pver1->Id();
		pcseg->node[1] = id_node1;
		if (pcseg->extn[0] == id_node1)
		{
			pcseg->extn[1] = pcseg->node[0];
			pcseg->extn[0] = id_node1;
		}
		else
			pcseg->extn[1] = pnode1->link[1];

		pver_old = player_region->GetVertex(pcseg_new->end[1]);
	}
	else
	{
		pcseg_new->end[0] = pcseg->end[0];
		pcseg_new->node[0] = pcseg->node[0];
		pcseg_new->extn[0] = pcseg->extn[0];
		pcseg_new->end[1]  = pver1->Id();
		pcseg_new->node[1] = id_node1;
		pcseg_new->extn[1] = id_node_ref;

		pcseg->end[0] = pver1->Id();
		pcseg->node[0] = id_node1;
		if (pcseg->extn[1] == id_node1)
		{
			pcseg->extn[0] = pcseg->node[1];
			pcseg->extn[1] = id_node1;
		}
		else
			pcseg->extn[0] = pnode1->link[0];

		pver_old = player_region->GetVertex(pcseg_new->end[0]);
	}
	pcseg_new->boundry_of[0] = pcseg->boundry_of[0];
	pcseg_new->boundry_of[1] = pcseg->boundry_of[1];

	// vertex
	if (!bself_closed)
		pver_old->DeleteCSeg(pcseg->Id());
	pver_old->AddSeg(pcseg_new->Id());

	pver1->AddSeg(pcseg->Id());
	pver1->AddSeg(pcseg_new->Id());

	return pcseg_new->Id();
}



int MCMC_MoveBoundary::CreateVertexAndBreakCSegs(MbNodeTopologyRecord &node, MbNodeTopologyRecord &node_top, MbNodeTopologyRecord &node_right)
{
	if (node.pver != NULL || node.NumAllConnections()<3)
		return -1;

	node.pver = player_region->GetVertex(player_region->NewVertex());
	assert(node.pver != NULL);
	node.pver->SetX(node.pnode->GetX());
	node.pver->SetY(node.pnode->GetY());
	player_region->mx_label_id_vertices(node.grid.Row(), node.grid.Col()) = node.pver->Id();

	int					 i,id_cseg_new=-1,id_node_nb;
	MCMC_Contour_Segment *pcseg_to_break;

	for (i=0; i<4; i++)
	{
		pcseg_to_break = node.GetCSegWithNeighbor(i);

		if (pcseg_to_break!=NULL)
		{
			id_node_nb = node.GetNodeNeightbor(i);
			if (id_node_nb==node_top.id_node || id_node_nb == node_right.id_node)
			{
				id_cseg_new = BreakContourSegment(pcseg_to_break, node.pver, node.id_node, id_node_nb);

				break;
			}
		}
	}

	MCMC_Contour_Segment *pcseg_new;

	pcseg_new = player_region->GetCSeg(id_cseg_new);
	UpdateCSegIdOnGrid(pcseg_new, pcseg_new->Id());

	return id_cseg_new;
}

void MCMC_MoveBoundary::ConnectContourSegments(void)
{
	MbNodeTopologyRecord *ptr_nodes[4];
	MCMC_Contour_Segment *pcseg_from,*pcseg_to_merge,*pcseg_to_delete;
	int					 i,j,k,m,temp;
	int				 degrees[4];

	// initialization
	ptr_nodes[0] = &node1;
	ptr_nodes[1] = &node1_to;
	ptr_nodes[2] = &node2_to;
	ptr_nodes[3] = &node2;
	for (k=0; k<4; k++)
		degrees[k] = ptr_nodes[k]->NumConnections();

	i = 3;
	j = 0;

	for (k=0; k<4; k++)
	{
		if (ptr_nodes[i]->pver != NULL)
		{
			while (j != i)
			{
				if (ptr_nodes[i]->connections_after[signs_connections[i]]==0)
				{
					pcseg_to_delete = player_region->GetCSeg(player_region->cseg_on_grid.CSegId(ptr_nodes[i]->grid, ptr_nodes[(i+1)%4]->grid));
					if (ptr_nodes[j]->pver!=NULL && pcseg_to_delete!=NULL)
					{
						pcseg_to_delete->ChangeStartOfRelatedRegion();
						// delete the contour segment
						ptr_nodes[i]->pver->DeleteCSeg(pcseg_to_delete->Id());
						ptr_nodes[j]->pver->DeleteCSeg(pcseg_to_delete->Id());
						player_region->DeleteCSegFromArray(pcseg_to_delete->Id());
						for (m=i; m!=j; m=(m+1)%4)
							player_region->cseg_on_grid.CSegId(ptr_nodes[m]->grid, ptr_nodes[(m+1)%4]->grid) = -1;
						break;
					}
					else
						// move to the next
						j = (j+1)%4;
				}
				else
				{
					if (ptr_nodes[j]->pver == NULL)
						j = (j+1)%4;	// move to the next
					else
					{
						pcseg_to_merge = player_region->GetCSeg(player_region->cseg_on_grid.CSegId(ptr_nodes[i]->grid, ptr_nodes[(i+1)%4]->grid));

						if (pcseg_to_merge == NULL && !(degrees[i]==2 || degrees[j]==2))
						{
							// create a new contour segment
							pcseg_to_merge = player_region->GetCSeg(player_region->NewCSeg());
							assert(pcseg_to_merge != NULL);

							pcseg_to_merge->end[0] = ptr_nodes[i]->pver->Id();
							pcseg_to_merge->end[1] = ptr_nodes[j]->pver->Id();
							pcseg_to_merge->node[0] = ptr_nodes[i]->id_node;
							pcseg_to_merge->extn[0] = ptr_nodes[(i+1)%4]->id_node;
							pcseg_to_merge->extn[1] = ptr_nodes[(j+3)%4]->id_node;
							pcseg_to_merge->node[1] = ptr_nodes[j]->id_node;
							for (m=i; m!=j; m=(m+1)%4)
								ptr_nodes[m]->pnode->link[0] = ptr_nodes[(m+1)%4]->id_node;
							for (m=j; m!=i; m=(m+3)%4)
								ptr_nodes[m]->pnode->link[1] = ptr_nodes[(m+3)%4]->id_node;

							// left and right regions
							pcseg_to_merge->boundry_of[0] = labels[left_right[i][0]];
							pcseg_to_merge->boundry_of[1] = labels[left_right[i][1]];

							// add contour segment to the list of vertices
							ptr_nodes[i]->pver->AddSeg(pcseg_to_merge->Id());
							ptr_nodes[j]->pver->AddSeg(pcseg_to_merge->Id());

							// update the record
							for (m=i; m!=j; m=(m+1)%4)
								player_region->cseg_on_grid.CSegId(ptr_nodes[m]->grid, ptr_nodes[m+1]->grid) = pcseg_to_merge->Id();
						}

						if (degrees[i]==2 || degrees[j]==2)
						{

							// to merge contour segments
							if (degrees[i]==2)
								temp = i;
							else
								temp = j;
							for (m=0; m<4; m++)
							{
								if (ptr_nodes[temp]->connections_after[m])
								{
									pcseg_from = ptr_nodes[temp]->GetCSegWithNeighbor(m);
									if (pcseg_from!=NULL && pcseg_from!=pcseg_to_merge)
										break;
								}
								else{
									pcseg_from = NULL; // Siyuan: suppress compiling error
								}
							}
							assert(pcseg_from != NULL);
							if (pcseg_to_merge != NULL)
								MergeSegments(pcseg_from, pcseg_to_merge, *ptr_nodes[i], *ptr_nodes[j]);
							else
								ExtendContour(pcseg_from, ptr_nodes, i, j);
						}
						break;
					}
				}
			}
		}

		i = (i+1)%4;
		j = (i+1)%4;
	}

	MCMC_AtomicRegion *paregion_test;
	LinkList<int> list_node_to_merge_cseg;

	// delete those vertices that have degree 2
	for (i=0; i<4; i++)
	{
		if (ptr_nodes[i]->pver != NULL)
		{
			if (degrees[i] <= 2)
			{
				if (ptr_nodes[i]->pver->Degree() > 1)
					// to merge the the contour segments
					list_node_to_merge_cseg.Insert(i);
			}
			else
			{
				assert(degrees[i] = ptr_nodes[i]->pver->Degree());
			}

			if (ptr_nodes[i]->pver->Degree() == 0)
			{
				player_region->DeleteVertexFromArray(ptr_nodes[i]->pver->Id());
				player_region->mx_label_id_vertices(ptr_nodes[i]->grid.Row(), ptr_nodes[i]->grid.Col()) = -1;
				ptr_nodes[i]->pver = NULL;
			}
		}
		if (ptr_nodes[i]->NumConnections()==0)
		{
			if (player_region->mx_label_id_nodes(ptr_nodes[i]->grid.Row(), ptr_nodes[i]->grid.Col()) >= 0)
			{
				player_region->DeleteNodeFromArray(player_region->mx_label_id_nodes(ptr_nodes[i]->grid.Row(), ptr_nodes[i]->grid.Col()));
				player_region->mx_label_id_nodes(ptr_nodes[i]->grid.Row(), ptr_nodes[i]->grid.Col()) = -1;
				ptr_nodes[i]->pnode = NULL;
			}
		}
		// update left and reight region on the contour segment
		if (ptr_nodes[i]->pver != NULL)
		{
			pcseg_from = player_region->GetCSeg(player_region->cseg_on_grid.CSegId(ptr_nodes[i]->grid, ptr_nodes[(i+1)%4]->grid));
			if (pcseg_from != NULL)
			{
				paregion_test = LayerRegion()->GetAtomicRegion(pcseg_from->GetLeftAtomicRegion());
				if ((paregion_test!=NULL && paregion_test->Id()!=labels[left_right[i][0]] && paregion_test->Id()!=labels[left_right[i][1]]) &&
					paregion_test->GetStartCSeg()==pcseg_from->Id())
					pcseg_from->ChangeStartOfRelatedRegion();

				paregion_test = LayerRegion()->GetAtomicRegion(pcseg_from->GetRightAtomicRegion());
				if ((paregion_test!=NULL && paregion_test->Id()!=labels[left_right[i][0]] && paregion_test->Id()!=labels[left_right[i][1]]) &&
					paregion_test->GetStartCSeg()==pcseg_from->Id())
					pcseg_from->ChangeStartOfRelatedRegion();


				if (pcseg_from->IsFromNode1ToNode2(ptr_nodes[i]->pnode, ptr_nodes[i]->id_node, ptr_nodes[(i+1)%4]->pnode, ptr_nodes[(i+1)%4]->id_node))
				{
					pcseg_from->boundry_of[0] = labels[left_right[i][0]];
					pcseg_from->boundry_of[1] = labels[left_right[i][1]];
				}
				else
				{
					assert(pcseg_from->IsFromNode1ToNode2(ptr_nodes[(i+1)%4]->pnode, ptr_nodes[(i+1)%4]->id_node, ptr_nodes[i]->pnode, ptr_nodes[i]->id_node));
					pcseg_from->boundry_of[1] = labels[left_right[i][0]];
					pcseg_from->boundry_of[0] = labels[left_right[i][1]];
				}
			}
		}
	}

	// to merge the the contour segments
	bool bgo;

	bgo = list_node_to_merge_cseg.GetFirst(i);
	while (bgo)
	{
		assert (ptr_nodes[i]->pver!=NULL && ptr_nodes[i]->pver->Degree()==2);

		pcseg_from = LayerRegion()->GetCSeg(ptr_nodes[i]->pver->GetFirstCSeg());
		pcseg_to_merge = LayerRegion()->GetCSeg(ptr_nodes[i]->pver->GetNextCSeg());
		
		UpdateCSegIdOnGrid(pcseg_to_merge, pcseg_from->Id());
		LayerRegion()->MergeSegments(pcseg_from->Id(), pcseg_to_merge->Id());

		if (pcseg_from->node[0]!= ptr_nodes[i]->id_node && 
			pcseg_from->node[1]!= ptr_nodes[i]->id_node)
			// to delete this vertex
			LayerRegion()->mx_label_id_vertices(ptr_nodes[i]->grid.Row(), ptr_nodes[i]->grid.Col()) = -1;

		bgo = list_node_to_merge_cseg.GetNext(i);
	}
	
}


bool MCMC_MoveBoundary::IsSpecialCase3(MCMC_Contour_Segment* pcseg)
{
	int num1=node1.NumConnections();
	int num1_to=node1_to.NumConnections();
	int num2=node2.NumConnections();
	int num2_to=node2_to.NumConnections();

	if (num2==0 && num2_to==0)
		return DeleteTwoNodes(pcseg, node1, node1_to, node2, node2_to);
	else if (num1==0 && num2==0)
		return DeleteTwoNodes(pcseg, node1_to, node2_to, node1, node2);
	else if (num1==0 && num1_to==0)
		return DeleteTwoNodes(pcseg, node2_to, node2, node1_to, node1);

	return false;
}

bool MCMC_MoveBoundary::DeleteTwoNodes(MCMC_Contour_Segment* pcseg, MbNodeTopologyRecord &node_keep1, MbNodeTopologyRecord &node_keep2, MbNodeTopologyRecord &node_del1, MbNodeTopologyRecord &node_del2)
{
	if (pcseg->IsFromNode1ToNode2(node_del1.pnode, node_del1.id_node, node_del2.pnode, node_del2.id_node))
	{
		node_keep1.pnode->link[0] = node_keep2.id_node;
		node_keep2.pnode->link[1] = node_keep1.id_node;

//		if (pcseg->node[0] == node_del2.id_node || pcseg->node[1]== node_del2.id_node)
//			assert(false);

		if (pcseg->node[0] == node_del1.id_node)
		{
			assert(node_del1.pver != NULL);
			node_del1.pver->SetX(node_keep1.pnode->GetX());
			node_del1.pver->SetY(node_keep1.pnode->GetY());

			player_region->mx_label_id_vertices(node_del1.grid.Row(), node_del1.grid.Col()) = -1;
			node_keep1.pver = node_del1.pver;
			node_del1.pver = NULL;

			pcseg->node[0] = node_keep1.id_node;
			pcseg->node[1] = node_keep1.id_node;
			pcseg->extn[0] = node_keep2.id_node;
			pcseg->extn[1] = node_keep1.pnode->link[1];

			player_region->mx_label_id_vertices(node_keep1.grid.Row(), node_keep1.grid.Col()) = node_keep1.pver->Id();
		}
		if (pcseg->node[0] == node_del2.id_node)
		{
			assert(node_del2.pver != NULL);
			node_del2.pver->SetX(node_keep2.pnode->GetX());
			node_del2.pver->SetY(node_keep2.pnode->GetY());

			player_region->mx_label_id_vertices(node_del2.grid.Row(), node_del2.grid.Col()) = -1;
			node_keep2.pver = node_del2.pver;
			node_del2.pver = NULL;

			pcseg->node[0] = node_keep2.id_node;
			pcseg->node[1] = node_keep2.id_node;
			pcseg->extn[0] = node_keep2.pnode->link[0];
			pcseg->extn[1] = node_keep1.id_node;

			player_region->mx_label_id_vertices(node_keep2.grid.Row(), node_keep2.grid.Col()) = node_keep2.pver->Id();
		}
		if (pcseg->extn[0] == node_del1.id_node)
			pcseg->extn[0] = node_keep2.id_node;
		if (pcseg->extn[1] == node_del2.id_node)
			pcseg->extn[1] = node_keep1.id_node;
	}
	else
	{
		node_keep2.pnode->link[0] = node_keep1.id_node;
		node_keep1.pnode->link[1] = node_keep2.id_node;

//		if (pcseg->node[0] == node_del1.id_node || pcseg->node[1]== node_del1.id_node)
//			assert(false);

		if (pcseg->node[0] == node_del2.id_node)
		{
			assert(node_del2.pver != NULL);
			node_del2.pver->SetX(node_keep2.pnode->GetX());
			node_del2.pver->SetY(node_keep2.pnode->GetY());

			player_region->mx_label_id_vertices(node_del2.grid.Row(), node_del2.grid.Col()) = -1;
			node_keep2.pver = node_del2.pver;
			node_del2.pver = NULL;

			pcseg->node[0] = node_keep2.id_node;
			pcseg->node[1] = node_keep2.id_node;
			pcseg->extn[0] = node_keep1.id_node;
			pcseg->extn[1] = node_keep2.pnode->link[1];

			player_region->mx_label_id_vertices(node_keep2.grid.Row(), node_keep2.grid.Col()) = node_keep2.pver->Id();
		}
		if (pcseg->node[0] == node_del1.id_node)
		{
			assert(node_del1.pver != NULL);
			node_del1.pver->SetX(node_keep1.pnode->GetX());
			node_del1.pver->SetY(node_keep1.pnode->GetY());

			player_region->mx_label_id_vertices(node_del1.grid.Row(), node_del1.grid.Col()) = -1;
			node_keep1.pver = node_del1.pver;
			node_del1.pver = NULL;

			pcseg->node[0] = node_keep1.id_node;
			pcseg->node[1] = node_keep1.id_node;
			pcseg->extn[0] = node_keep1.pnode->link[0];
			pcseg->extn[1] = node_keep2.id_node;

			player_region->mx_label_id_vertices(node_keep1.grid.Row(), node_keep1.grid.Col()) = node_keep1.pver->Id();
		}
		if (pcseg->extn[0] == node_del2.id_node)
			pcseg->extn[0] = node_keep1.id_node;
		if (pcseg->extn[1] == node_del1.id_node)
			pcseg->extn[1] = node_keep2.id_node;
	}
	// delete the two nodes
	player_region->DeleteNodeFromArray(node_del1.id_node);
	player_region->mx_label_id_nodes(node_del1.grid.Row(), node_del1.grid.Col()) = -1;
	player_region->DeleteNodeFromArray(node_del2.id_node);
	player_region->mx_label_id_nodes(node_del2.grid.Row(), node_del2.grid.Col()) = -1;
	player_region->cseg_on_grid.CSegId(node_keep1.grid, node_keep2.grid) = pcseg->Id();
	player_region->cseg_on_grid.CSegId(node_keep1.grid, node_del1.grid) = -1;
	player_region->cseg_on_grid.CSegId(node_del1.grid, node_del2.grid) = -1;
	player_region->cseg_on_grid.CSegId(node_del2.grid, node_keep2.grid) = -1;

	return true;
}

void MCMC_MoveBoundary::ExtendContour(MCMC_Contour_Segment *pcseg, MbNodeTopologyRecord *ptr_nodes[4], const int i, const int j)
{
	bool		bfrom_i_to_j;
	MCMC_Node	*pnode_extn;
	int choice;

	if (pcseg->node[0]==ptr_nodes[i]->id_node && pcseg->node[1]==ptr_nodes[j]->id_node)
	{
		if (ptr_nodes[i]->NumConnections()<=ptr_nodes[j]->NumAllConnections())
			choice = 0;
		else
			choice = 3;
	}
	else if (pcseg->node[1]==ptr_nodes[i]->id_node && pcseg->node[0] == ptr_nodes[j]->id_node)
	{
		if (ptr_nodes[i]->NumConnections()<=ptr_nodes[j]->NumAllConnections())
			choice = 1;
		else
			choice = 2;
	}
	else if (pcseg->node[0] == ptr_nodes[i]->id_node)
		choice = 0;
	else if (pcseg->node[1] == ptr_nodes[i]->id_node)
		choice = 1;
	else if (pcseg->node[0] == ptr_nodes[j]->id_node)
		choice = 2;
	else
		choice = 3;
	
	switch (choice)
	{
	case 0:
			bfrom_i_to_j = false;

			ptr_nodes[i]->pnode->link[0] = pcseg->extn[0];
			pnode_extn = player_region->GetNode(pcseg->extn[0]);
			pnode_extn->link[1] = pcseg->node[0];

			pcseg->end[0] = ptr_nodes[j]->pver->Id();
			pcseg->node[0] = ptr_nodes[j]->id_node;
			pcseg->extn[0] = ptr_nodes[(j+3)%4]->id_node;

			ptr_nodes[i]->pver->DeleteCSeg(pcseg->Id());
			ptr_nodes[j]->pver->AddSeg(pcseg->Id());
			break;
	case 1:
			bfrom_i_to_j = true;

			ptr_nodes[i]->pnode->link[1] = pcseg->extn[1];
			pnode_extn = player_region->GetNode(pcseg->extn[1]);
			pnode_extn->link[0] = pcseg->node[1];

			pcseg->end[1] = ptr_nodes[j]->pver->Id();
			pcseg->node[1] = ptr_nodes[j]->id_node;
			pcseg->extn[1] = ptr_nodes[(j+3)%4]->id_node;

			ptr_nodes[i]->pver->DeleteCSeg(pcseg->Id());
			ptr_nodes[j]->pver->AddSeg(pcseg->Id());
			break;
	case 2:
			bfrom_i_to_j = true;

			ptr_nodes[j]->pnode->link[0] = pcseg->extn[0];
			pnode_extn = player_region->GetNode(pcseg->extn[0]);
			pnode_extn->link[1] = pcseg->node[0];

			pcseg->end[0] = ptr_nodes[i]->pver->Id();
			pcseg->node[0] = ptr_nodes[i]->id_node;
			pcseg->extn[0] = ptr_nodes[(i+1)%4]->id_node;

			ptr_nodes[j]->pver->DeleteCSeg(pcseg->Id());
			ptr_nodes[i]->pver->AddSeg(pcseg->Id());
			break;
	case 3:
			assert(pcseg->node[1] == ptr_nodes[j]->id_node);

			bfrom_i_to_j = false;

			ptr_nodes[j]->pnode->link[1] = pcseg->extn[1];
			pnode_extn = player_region->GetNode(pcseg->extn[1]);
			pnode_extn->link[0] = pcseg->node[1];

			pcseg->end[1] = ptr_nodes[i]->pver->Id();
			pcseg->node[1] = ptr_nodes[i]->id_node;
			pcseg->extn[1] = ptr_nodes[(i+1)%4]->id_node;

			ptr_nodes[j]->pver->DeleteCSeg(pcseg->Id());
			ptr_nodes[i]->pver->AddSeg(pcseg->Id());
			break;
	default: assert(false);
	}

	int m;

	if (bfrom_i_to_j)
	{
		for (m=i; m!=j; m=(m+1)%4)
		{
			ptr_nodes[m]->pnode->link[0] = ptr_nodes[(m+1)%4]->id_node;
			player_region->cseg_on_grid.CSegId(ptr_nodes[m]->grid, ptr_nodes[(m+1)%4]->grid) = pcseg->Id();
		}
		for (m=j; m!=i; m=(m+3)%4)
			ptr_nodes[m]->pnode->link[1] = ptr_nodes[(m+3)%4]->id_node;
	}
	else
	{
		for (m=j; m!=i; m=(m+3)%4)
		{
			ptr_nodes[m]->pnode->link[0] = ptr_nodes[(m+3)%4]->id_node;
			player_region->cseg_on_grid.CSegId(ptr_nodes[m]->grid, ptr_nodes[(m+3)%4]->grid) = pcseg->Id();
		}
		for (m=i; m!=j; m=(m+1)%4)
			ptr_nodes[m]->pnode->link[1] = ptr_nodes[(m+1)%4]->id_node;
	}
}


bool MCMC_MoveBoundary::CheckConsistencyOfTopologyRecord(void)
{
	Raster<int>		mx_label_id_aregions;
	mcmcMatrix<int>	mx_label_id_nodes;
	mcmcMatrix<int>	mx_label_id_vertices;
	MCMC_CSegOnGrid	cseg_on_grid;

	mx_label_id_aregions	= player_region->mx_label_id_aregions;
	mx_label_id_nodes		= player_region->mx_label_id_nodes;
	mx_label_id_vertices	= player_region->mx_label_id_vertices;
	cseg_on_grid			= player_region->cseg_on_grid;

	int i,j;

	player_region->CreateTopologyRecords();

	for (j=0; j<mx_label_id_aregions.rows(); j++)
		for (i=0; i<mx_label_id_aregions.cols(); i++)
			if (mx_label_id_aregions(j,i) != player_region->mx_label_id_aregions(j,i))
			{
				assert(false);
				return false;
			}

	for (j=0; j<mx_label_id_vertices.rows(); j++)
		for (i=0; i<mx_label_id_vertices.cols(); i++)
			if (mx_label_id_vertices(j,i) != player_region->mx_label_id_vertices(j,i))
			{
				assert(false);
				return false;
			}

	for (j=0; j<mx_label_id_nodes.rows(); j++)
		for (i=0; i<mx_label_id_nodes.cols(); i++)
			if (mx_label_id_nodes(j,i) != player_region->mx_label_id_nodes(j,i))
			{
				assert(false);
				return false;
			}

	for (j=0; j<cseg_on_grid.mx_id_cseg_row.rows(); j++)
		for (i=0; i<cseg_on_grid.mx_id_cseg_row.cols(); i++)
			if (cseg_on_grid.mx_id_cseg_row(j,i) != player_region->cseg_on_grid.mx_id_cseg_row(j,i))
			{
				assert(false);
				return false;
			}

	for (j=0; j<cseg_on_grid.mx_id_cseg_col.rows(); j++)
		for (i=0; i<cseg_on_grid.mx_id_cseg_col.cols(); i++)
			if (cseg_on_grid.mx_id_cseg_col(j,i) != player_region->cseg_on_grid.mx_id_cseg_col(j,i))
			{
				assert(false);
				return false;
			}

	return true;
}


void MCMC_MoveBoundary::RandomMove(void)
{
	RF						rf;
	RF_uniform				rf_end;
	mcmcVector<int>				vc_ids;
	MCMC_Contour_Segment	*pcseg;
	int						k;

//	pcseg = player_region->GetCSeg(31);
//	MoveNodes(pcseg, 1335, 1334, MB_CSEG_LEFT);

	rf_end.Set(0, 1, 1);
	for (int i=0; i<500; i++)
	{
		vc_ids.SetRowVector(player_region->NumCSegments());
		vc_ids.InitValue(-1);
		rf.Set(0, vc_ids.size()-1, 1);

		k = 0;
		pcseg = player_region->GetCSeg(player_region->GetFirstCSeg());
		while (pcseg != NULL)
		{
			rf.AddOneBin(k, 1.0);
			vc_ids(k++) = pcseg->Id();
			pcseg = player_region->GetCSeg(player_region->GetNextCSeg());
		}
		rf.normalize();

		k = (int)rf.SamplingNonSetCdf();

		pcseg = player_region->GetCSeg(vc_ids(k));
		if (pcseg != NULL)
		{
			if ((int)rf_end.Sampling() == 0)
			{
				if ((int)rf_end.Sampling() == 0)
					MoveNodes(pcseg, pcseg->node[0], pcseg->extn[0], MB_CSEG_LEFT);
				else
					MoveNodes(pcseg, pcseg->node[0], pcseg->extn[0], MB_CSEG_RIGHT);
			}
			else
			{
				if ((int)rf_end.Sampling() == 0)
					MoveNodes(pcseg, pcseg->node[1], pcseg->extn[1], MB_CSEG_LEFT);
				else
					MoveNodes(pcseg, pcseg->node[1], pcseg->extn[1], MB_CSEG_RIGHT);
			}
		}
	}

}
